package com.sise.Tree;

/**
 *      116. 填充每个节点的下一个右侧节点指针
 *
 *      给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
 *      填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *      初始状态下，所有 next 指针都被设置为 NULL。
 *
 */
public class _116_connect {
    public Node connect(Node root) {
        // 由于是完美二叉树，所以 左节点不存在的情况下，右节点肯定不存在，故此不用判断
        if (root == null || root.left == null) {
            return root;
        }

        // 1、让 root 的左节点指向右节点
        root.left.next = root.right;

        // 2、这里是 跨节点连接，root 的右节点 -> root.next 节点的左节点
        if (root.next != null){
            root.right.next = root.next.left;
        }

        connect(root.left);
        connect(root.right);
        return root;
    }
}
